Graph analysis is an important emerging workload area. Such analysis is used to extract valuable information from large graph instances (representing people and their connections, but increasingly also places, actions, or events). The current technology includes a stack built on top of a relational database and is not well suited for graph analysis.
A typical graph is a set of nodes or vertices connected by edges each of which has a particular direction. A computer-represented graph is a data structure, such as an adjacency list or adjacency matrix, in which a representation of the graph is stored. In an adjacency list of a graph G=(V, E) with vertices V and edges E, the adjacency list is an array of lists, one list for each vertex. The list for each vertex contains the names of all of the vertices adjacent to that vertex. In an adjacency matrix of a graph G=(V, E), the elements are all possible pairs of vertices. If an edge exists between a pair of vertices, the element in the matrix is marked.
A graph analysis program often includes a series of neighborhood iterating operations. These operations iterate over vertices that are neighborhood vertices to other vertices in the directed graph while reading and writing data associated with the vertices and their neighborhood vertices.
In some cases, a neighborhood iterating operation can be transformed into a functionally equivalent operation by altering the direction of the edges in the graph. This transformation is sometimes called an edge-flipping transformation, but often such a transformation is not feasible because altering the graph either is not permitted or takes too much time.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.